package com.waiting.thread;

import java.util.ArrayList;
import java.util.List;

/**
 * @Description
 * @Author bjweitingting
 * @Date 2019/3/8
 **/
public class UniqueBinarySearchTreesII95 {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return new ArrayList<>();
        }
        List<TreeNode> results = generateTrees(1, n);
        return results;
    }

    private List<TreeNode> generateTrees(int begin, int end) {
        List<TreeNode> results = new ArrayList<>();
        if (begin > end) {
            results.add(null);
            return results;
        }
        if (begin == end) {
            results.add(new TreeNode(begin));
            return results;
        }

        for (int i = begin; i <= end; i++) {
            //以i元素为根
            //左边的元素是 [begin,i-1]
            List<TreeNode> lstLeft = generateTrees(begin, i - 1);
            //右边的元素是 [i+1，end]
            List<TreeNode> lstRight = generateTrees(i + 1, end);

            for (int j = 0; j < lstLeft.size(); j++) {
                TreeNode lNode = lstLeft.get(j);
                for (int k = 0; k < lstRight.size(); k++) {
                    TreeNode rNode = lstRight.get(k);
                    TreeNode root = new TreeNode(i);
                    root.left = lNode;
                    root.right = rNode;
                    results.add(root);
                }
            }
        }
        return results;
    }
}
